会议室 III(Leetcode 2402)

题目分析

   本题是周赛的第四题，思路还是比较清晰的，跟着样例模拟一下就能解答。

暴力

暴力解法也可以，记录每个会议室的结束时间，每次遍历n个会议室，如果有空闲，则使用索引最小的会议室。如果都没有空闲，则寻找最早结束的会议室。将该会议安排在这个会议室中，并更新这个会议室的结束时间即可。

算法的时间复杂度为$ O(mn) $，空间复杂度为O(n)。

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        long[] last = new long[n];
        int[] cnt = new int[n];
        Arrays.sort(meetings, Comparator.comparingInt(o -> o[0]));
        for (int[] meet : meetings) {
            for (int i = 0; i < n; i++) {
                if (meet[0] >= last[i]) {
                    last[i] = meet[1];
                    cnt[i]++;
                    break;
                }
                if (i == n - 1) {
                    int idx = findMiniIndex(last);
                    last[idx] += meet[1] - meet[0];
                    cnt[idx]++;
                }
            }
        }
        return findMaxIndex(cnt);
    }

    private int findMiniIndex(long[] arr) {
        long mini = arr[0];
        int idx = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < mini) {
                mini = arr[i];
                idx = i;
            }
        }
        return idx;
    }

    private int findMaxIndex(int[] arr) {
        int max = arr[0];
        int idx = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                idx = i;
            }
        }
        return idx;
    }
}

小顶堆

小顶堆的思想是根据结束时间将会议室放在堆中，则堆顶的会议室就是结束最早的会议室。

还需要维护一个堆，表示当前空闲的会议室，根据编号将空闲的会议室也放入另一个堆中。

思路就非常清晰了，记空闲的会议室是spaceRoom，记占用的会议室为useRoom。

spaceRoom根据编号排序，useRoom根据结束时间排序。每次会议来的时候，更新useRoom和spaceRoom，因为useRoom中的堆顶，可能已经结束了，因此要加入到spaceRoom中。

算法的时间复杂度为$ O(mlog(n)) $，空间复杂度为O(n)。

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        PriorityQueue<int[]> spaceRoom = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (int i = 0; i < n; i++) {
            spaceRoom.add(new int[]{0, i});
        }
        Arrays.sort(meetings, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<int[]> useRoom = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int m = meetings.length;
        int[] cnt = new int[n];
        for (int i = 0; i < m; i++) {
            while (!useRoom.isEmpty() && useRoom.peek()[0] <= meetings[i][0]) {
                spaceRoom.add(useRoom.poll());
            }
            int[] currentRoom = spaceRoom.isEmpty() ? useRoom.poll() : spaceRoom.poll();
            currentRoom[0] = Math.max(meetings[i][0], currentRoom[0]) + meetings[i][1] - meetings[i][0];
            cnt[currentRoom[1]]++;
            useRoom.add(currentRoom);
        }
        int max = Arrays.stream(cnt).max().getAsInt();
        for (int i = 0; i < n; i++) {
            if (cnt[i] == max) {
                return i;
            }
        }
        return -1;
    }
}

刷题总结

  题目难度不大，如果能在有限的时间里将暴力的思路写出来，也是挺不错的。